1. Field of the Invention
The present invention generally relates to digital filters and, more particularly, to Finite Impulse Response (FIR) filters.
2. State of the Art
In conventional practice, computations involved in realizing a FIR filter have been memory-access intensive. One data output point of a FIR filter is calculated as ##EQU1## and a succeeding output data point is calculated as ##EQU2## where A.sub.i is one of a series of coefficients defining a windowing function of the filter and X.sub.i is one of a series of input data points.
FIG. 1 shows a known system for performing the foregoing computations. In the system, the coefficients A.sub.i and the input data points X.sub.i are stored in a random access memory 11. The RAM 11 is addressed by an address generator 13 to output corresponding A.sub.i and X.sub.i to a multiplier 15 to form the product A.sub.i X.sub.i. The product A.sub.i X.sub.i is input to either an adder 17 or, in the case i=1, to an accumulator register 19 through a multiplexer 16. When i.notident.1, the previous sum ##EQU3## stored in the accumulator register 19 is added to the current product A.sub.i X.sub.i in the adder 17 and the cumulative result is stored in the accumulator register 19 through the multiplexer 16. After the sum of the N products has been accumulated in the accumulator register 19, the contents of the accumulator register 19 is output as an output data point. In practice, the coefficients A.sub.i may either be fixed in the case of a non-adaptive filter or may be varied between the calculation of output data points in the case of an adaptive filter.
The system of FIG. 1 requires the address generator 13 to generate 2N addresses per output data point despite the fact that of the 2N operands involved in the calculation, only one of the operands, a new input data point, may differ from the operands involved in the previous calculation.
To address the foregoing problem, various modifications to the basic circuit arrangement of FIG. 1 have been proposed. For example, in U.S. Pat. No. 5,297,069, incorporated herein by reference, a circuit is disclosed for realizing a FIR filter that is similar to the circuit of FIG. 1 except that it additionally includes a buffer memory 20 between the RAM 11 and the multiplier 15, as shown in FIG. 2. Output data points of a digital filter are calculated by storing input data points in an addressable memory and accessing the addressable memory to supply a new input data point exactly once for each output data point after a first output data point and storing each input data point in a first recirculating memory for so long as that input data point is needed to calculate a next output data point. The input data points stored in the first recirculating memory (recirculating shift register 21) are used to calculate output data points. Furthermore, coefficients are stored in a second recirculating memory (recirculating shift register 23) and used to calculate the output data points. The recirculating shift register 21 has one less stage than the recirculating shift register 23 in order to "shift" the series of input data points X.sub.i with respect to the series of coefficients A.sub.i. In the circuit of FIG. 2, only one memory access is required per output data point.
The circuit of FIG. 2 can be modified to realize special cases of the general FIR filter in a computationally efficient manner. For example, in the case of an odd FIR filter, even-indexed coefficients A.sub.2, A.sub.4, A.sub.6 . . . are uniformly zero. Therefore, imagining the series of coefficients being "shifted across" the longer series of input data points after the calculation of each output data point, the zero even-indexed coefficients will first be aligned with even-indexed input data points, then with odd-indexed input data points, then again with even-indexed input data points, and so forth such that half the X.sub.i 's are not used to calculate each output. The X.sub.i 's can therefore be split into two recirculating shift registers, one holding even-indexed X.sub.i and the other holding odd-indexed X.sub.i. The shift registers are then used alternately for every other output calculation.
The circuit of FIG. 2 may also be modified to realize a symmetric FIR filter. In a symmetric FIR filter, the first and last coefficients A.sub.1 and A.sub.n are equal as are the second and next to last coefficients A.sub.2 and A.sub.n-1, and so forth. To realize a symmetric FIR filter in a computationally efficient manner, only one of each pair of equal coefficients is stored and the input data points corresponding to the pair of equal coefficients are added and multiplied by the single stored coefficient since A.sub.1 X.sub.1 +A.sub.n X.sub.n =A.sub.1 (X.sub.1 +X.sub.n) for A.sub.1 =A.sub.n. Modified circuits for realizing odd and symmetric FIR filters are described in the aforementioned U.S. Pat. No. 5,297,069.
Special forms of the symmetric FIR filter include the polyphase interpolating symmetric FIR filter and the polyphase decimating symmetric FIR filter. In the polyphase interpolating symmetric FIR filter the N input samples X.sub.i are composed of recurring sequences of one non-zero sample followed by D-1 zero samples. In the polyphase decimating symmetric FIR filter the N input samples X.sub.i are composed of recurring sequences of one wanted sample followed b samples. In both cases, since it is known a priori that the result of most multiplies will either be zero or will be "thrown away", this characteristic of the input samples allows the N-point convolution to be rewritten as D N/D-point convolutions. Take for example the case of a 16-point interpolating symmetric filter with the following coefficients and input sequence:
TABLE I __________________________________________________________________________ COEFFICIENTS A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 A.sub.5 A.sub.6 A.sub.7 A.sub.7 A.sub.6 A.sub.5 A.sub.4 A.sub.3 A.sub.2 A.sub.1 A.sub.0 INPUT SEQUENCE 0 0 0 X.sub.3 0 0 0 X.sub.2 0 0 0 X.sub.1 0 0 0 X.sub.0 __________________________________________________________________________
Because of the characteristics of the input sequence, the N=16-point convolution can be rewritten as N/D (16/4 =4) four-point convolutions. In particular, note that as the data input sequence is "shifted across" the coefficient sequence, the coefficients to be multiplied by non-zero data values occur in repeating groups of four, i.e., {A.sub.0, A.sub.4, A.sub.7, A.sub.3 }, {A.sub.3, A.sub.7, A.sub.4, A.sub.0 }, {A.sub.2, A.sub.6, A.sub.5, A.sub.1 } and {A.sub.1, A.sub.5, A.sub.6, A.sub.2 }. The convolution may therefore be written as follows: ##EQU4##
A generalized block diagram of a polyphase interpolating filter is shown in FIG. 3. The input data points are input in common to the individual filter phases s f.sub.0, f.sub.1, f.sub.2 and f.sub.3. A commutator is used to sequentially select the output point of one of the filter phases as the output point of the overall polyphase interpolating filter.
In the case of a polyphase decimating filter, on the other hand, the N-point convolution to be again be rewritten as D N/D-point convolutions, but the filter utilizes a different structure. Take for example the case of a 16-point, decimate-by-four symmetric filter with the following coefficients and input sequence:
TABLE II __________________________________________________________________________ COEFFICIENTS A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 A.sub.5 A.sub.6 A.sub.7 A.sub.7 A.sub.6 A.sub.5 A.sub.4 A.sub.3 A.sub.2 A.sub.1 A.sub.0 INPUT SEQUENCE X.sub.15 X.sub.14 X.sub.13 X.sub.12 X.sub.11 X.sub.10 X.sub.9 X.sub.8 X.sub.7 X.sub.6 X.sub.5 X.sub.4 X.sub.3 X.sub.2 X.sub.1 X.sub.0 __________________________________________________________________________
Because of the characteristics of the input sequence, the N=16-point convolution can be rewritten as N/D (16/4=4) four-point convolutions. In particular, note that as the data input sequence is "shifted across" the coefficient sequence, for each shift the results of which are used, three additional shifts occur, both before and after, the results of which are thrown away. A relationship is therefore created between groups of coefficients that are multiplied by the same data points at different instants. On this basis, the coefficients may be grouped as {A.sub.0, A.sub.4, A.sub.7, A.sub.3 }, {A.sub.3, A.sub.7, A.sub.4, A.sub.0 }, {A.sub.2, A.sub.6, A.sub.5, A.sub.1 } and {A.sub.1, A.sub.5, A.sub.6, A.sub.2 }, the same groups as in the interpolating filter case. The convolution, however, is written as follows: ##EQU5##
A generalized block diagram of a polyphase decimating filter is shown in FIG. 4. The input data points are distributed between the individual filter phases s f.sub.0, f.sub.1, f.sub.2 and f.sub.3 using a commutator. One output point of the overall polyphase interpolating filter is formed by summing the output points of each of the individual filter phases.
In the case of both interpolation and decimation, breaking the overall convolution calculation into smaller pieces allows greater computational efficiency to be obtained. However, while the initial N-point filter may be symmetric and can be easily sequenced, the individual N/D-point polyphase filters are not symmetric. This lack of symmetry requires an address sequencer of increased complexity. Furthermore, a filter may require more multiply/accumulate operations than can be accomplished by a single multiplier. The usual approach in such a situation is to add a second multiplier. This approach results in a factor of two increase in area to implement the filter.